// 给定一个无序的整数数组，找到其中最长上升子序列的长度。

// 示例:

// 输入: [10,9,2,5,3,7,101,18]
// 输出: 4 
// 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
// 说明:

// 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
// 你算法的时间复杂度应该为 O(n2) 。
// 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

#include <vector>

using namespace std;

// 时间复杂度O(n^2)
// 维护一个一维dp数组，其中dp[i]表示以nums[i]为结尾的最长递增子串的长度，
// 对于每一个nums[i]，我们从第一个数再搜索到i，如果发现某个数小于nums[i]，
// 我们更新dp[i]，更新方法为dp[i] = max(dp[i], dp[j] + 1)，
// 即比较当前dp[i]的值和那个小于num[i]的数的dp值加1的大小，
// 我们就这样不断的更新dp数组，到最后dp数组中最大的值就是我们要返回的LIS的长度
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j)
                if (nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j]+1);
            res = max(res, dp[i]);
        }
        return res;
    }
};

// 时间复杂度O(nlogn)
// 二分查找法，思路是先建立一个空的dp数组，然后开始遍历原数组，
// 对于每一个遍历到的数字，我们用二分查找法在dp数组找第一个不小于它的数字，
// 如果这个数字不存在，那么直接在dp数组后面加上遍历到的数字，
// 如果存在，则将这个数字更新为当前遍历到的数字，最后返回dp数字的长度即可，
// 注意的是，跟上面的方法一样，特别注意的是dp数组的值可能不是一个真实的LIS。
class Solution1 {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            int left = 0, right = dp.size();
            // 二分查找法在dp数组找第一个不小于它的数字
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (dp[mid] < nums[i])
                    left = mid + 1;
                else
                    right = mid;
            }
            if (right == dp.size()) // 如果这个数字不存在，那么直接在dp数组后面加上遍历到的数字
                dp.push_back(nums[i]);
            else // 如果存在，则将这个数字更新为当前遍历到的数字
                dp[right] = nums[i];
        }
        return dp.size();
    }
};

/* 动态规划
dp[i]表示以当前数字结尾的最长上升子序列
时间复杂度：O(n^2)
空间复杂度：O(n)
*/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        for (int i{1}; i < n; ++i) {
            for (int j{i-1}; j >= 0; --j) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        int res{0};
        for (auto& i : dp) {
            res = max(res, i);
        }
        return res;
    }
};

/* 贪心 + 二分查找
如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，
因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
维护一个数组 d[i] ，表示长度为 i 的最长上升子序列的末尾元素的最小值，
用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1]=nums[0]
时间复杂度：O(nlogn)
空间复杂度：O(n)
*/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        int len{1};
        vector<int> d(n + 1, 0);
        d[len] = nums[0];
        for (int i{1}; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1;
                int r = len;
                // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                int pos = 0;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
};